﻿#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>

using namespace std;

static void merge(int* pArr, int left, int middle, int right)
{
    int* mergedArr = (int*)malloc((right - left + 1) * sizeof(int));
    int index = 0;
    int leftIndex = left;
    int rightIndex = middle + 1;
    while (leftIndex <= middle && rightIndex <= right)
    {
        mergedArr[index++] = (pArr[leftIndex] <= pArr[rightIndex]) ? pArr[leftIndex++] : pArr[rightIndex++];
    }

    while (leftIndex <= middle)
    {
        mergedArr[index++] = pArr[leftIndex++];
    }

    while (rightIndex <= right)
    {
        mergedArr[index++] = pArr[rightIndex++];
    }

    for (int i = left; i <= right; i++)
    {
        pArr[i] = mergedArr[i - left];
    }

    free(mergedArr);
}

static void mergeSort(int* pArr, int left, int right)
{
    if (left >= right) return;

    int middle = left + ((right - left) >> 1);
    mergeSort(pArr, left, middle);
    mergeSort(pArr, middle + 1, right);
    merge(pArr, left, middle, right);
}

int main_MergeSort() {
    int arr[] = { 3, 7, 8, 46, 0, 2, 50, 3, 4, 12, 99, 10, 9, 75, 18 };
    int size = sizeof(arr) / sizeof(int);
    mergeSort(arr, 0, size - 1);

    for (int i = 0; i < size; i++)
    {
        printf("arr[%d]=%d\n", i, arr[i]);
    }

    return 0;
}